/**
 * 
 */
package cn.edu.cqu.bysj.wm.ago.anlys;

import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.neo4j.graphdb.GraphDatabaseService;
import org.neo4j.graphdb.Node;
import org.neo4j.graphdb.Relationship;
import org.neo4j.tooling.GlobalGraphOperations;
import org.ujmp.core.Matrix;

import cn.edu.cqu.bysj.wm.ago.gn.GN;
import cn.edu.cqu.bysj.wm.ago.gn.HierarchyTree;
import cn.edu.cqu.bysj.wm.util.NodeComparator;

/**
 * @author Meng
 * 
 */
public class ModularityGN {

	private static GraphDatabaseService gdb;
	private static HierarchyTree hTree;
	private static Matrix M;
	private static long n, e;

	// map of node id and its degree
	private static Map<Long, Integer> nodeDegree;

	// map of node id and community id it belongs to
	private static Map<Long, Long> nodeCommunity;

	// map of depth and communtiys in this depth
	public static Map<Integer, List<Node>> depthCommunity;

	// map of depth and modularity value
	public static Map<Integer, Float> Qs;

	// community ids vs nodes of the best result
	public static Map<Long, List<Node>> result;

	// max Q value
	public static float maxQ;
	// the depth max Q in
	public static int depth;

	/**
	 * calc modularities of depths in a htree
	 * 
	 * @param gn
	 */
	public static void calculate(GN gn) {

		nodeDegree = new HashMap<Long, Integer>();
		depthCommunity = new HashMap<Integer, List<Node>>();
		nodeCommunity = new HashMap<Long, Long>();
		Qs = new HashMap<Integer, Float>();
		result = new HashMap<Long, List<Node>>();

		gdb = gn.gdb;
		M = gn.matrix;
		hTree = gn.tree;
		n = gn.n;
		e = gn.e;

		calcDegree();
		calcAccDepth();
		bestResult();
	}

	/**
	 * calculate molularity according to depth
	 */
	private static void calcAccDepth() {

		for (int i = 0; i <= hTree.getDepth(); i++) {

			// get the communitys of depth i
			List<Node> list = hTree.getCommunitysByDepth(i);
			Collections.sort(list, new NodeComparator());
			depthCommunity.put(i, list);

			calcNodeCommunity(list);

			Qs.put(i, calcQ(list.size()));
		}
	}

	/**
	 * put the node and the community it belongs to map
	 * 
	 * @param list
	 *            node list
	 */
	private static void calcNodeCommunity(List<Node> list) {

		nodeCommunity.clear();

		for (Node node : list) {
			long cid = (Long) node.getId();
			for (Node n : hTree.communitys.get(cid))
				nodeCommunity.put(n.getId(), cid);
		}
	}

	/**
	 * find the max modularity value and the depth it in
	 */
	private static void bestResult() {

		maxQ = Collections.max(Qs.values());
		for (int i : Qs.keySet()) {
			if (Qs.get(i).equals(maxQ)) {
				depth = i;
				break;
			}
		}

		for (Node node : depthCommunity.get(depth)) {
			result.put(node.getId(), hTree.communitys.get(node.getId()));
		}
	}

	/**
	 * caluculate modularity of a depth
	 * 
	 * @param cn
	 *            community number
	 * @return Q
	 */
	private static float calcQ(int cn) {

		float Q = 0;
		for (int k = 1; k <= cn; k++) {
			float ak = 0;
			float ekk = 0;
			for (long i = 1; i <= n; i++) {
				ak += nodeDegree.get(i) * include(i, k);
				for (long j = 1; j <= n; j++) {
					ekk += M.getAsInt(i - 1, j - 1) * include(i, k)
							* include(j, k);
				}
			}
			ekk /= (2 * e);
			ak /= (2 * e);
			float ak2 = (float) Math.pow(ak, 2);
			Q += ekk - ak2;
		}
		return Q;
	}

	/**
	 * jude if node belongs to community or not
	 * 
	 * @param nid
	 *            node id
	 * @param cid
	 *            community id
	 * @return 1 or 0
	 */
	private static int include(long nid, long cid) {

		if (nodeCommunity.containsKey(nid)) {
			if (nodeCommunity.get(nid).equals(cid))
				return 1;
			else
				return 0;
		}
		return 0;
	}

	/**
	 * calculate the degree of each node
	 */
	private static void calcDegree() {

		for (Node node : GlobalGraphOperations.at(gdb).getAllNodes()) {
			int deg = 0;
			for (@SuppressWarnings("unused")
			Relationship rel : node.getRelationships()) {
				deg++;
			}
			nodeDegree.put(node.getId(), deg);
		}
	}
}
